import javax.swing.tree.TreeNode;
import java.util.HashMap;

class Solution03 {
	/** 
	 * 哈希表的键为当前节点到根节点的和，值为该前缀和出现的次数
	 */
	HashMap<Integer, Integer> prefixSum;

	/**
	 * 利用前缀和思想
	 */
	public int pathSum(TreeNode root, int targetSum){
		prefixSum = new HashMap<>();
		// 空路径
		prefixSum.put(0, 1);
		return dfs(root, targetSum, 0);
	}

	public int dfs(TreeNode root, int targetSum, int curSum){
		if(root == null){
			return 0;
		}
		int count = 0;
		// 当前节点的前缀和
		curSum += root.val;
		// 查找符合条件的前缀和出现的个数
		count = prefixSum.getOrDefault(curSum - targetSum, 0);
		// 将当前前缀和统计到哈希表
		prefixSum.put(curSum, prefixSum.getOrDefault(curSum, 0) + 1);

		count += dfs(root.left, targetSum, curSum);
		count += dfs(root.right, targetSum, curSum);

		prefixSum.put(curSum, prefixSum.get(curSum) - 1);

		return count;
	}
}
